#include <stdio.h>
#include <stdlib.h>
#define ElemType char
typedef struct ThreadNode
{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; // 1为线索，0为孩子
} ThreadNode, *ThreadTree;
void PreCreateThreadTree(ThreadTree *);       // 先序遍历创建二叉链表树
void visitAndBuildThread(ThreadNode *);       // 访问建立线索
void InThread(ThreadTree);                    // 中序线索化
void CreateInThread(ThreadTree);              // 中序线索化
void PreThread(ThreadTree);                   // 先序线索化
void CreatePreThread(ThreadTree);             // 先序线索化
void PostThread(ThreadTree);                  // 后序线索化
void CreatePostThread(ThreadTree);            // 后序线索化
void visit(ThreadNode *);                     // 访问输出结点
ThreadNode *Firstnode(ThreadNode *);          // 找到以P为根的子树中第一个被中序遍历的结点
ThreadNode *Nextnode(ThreadNode *);           // 在中序线索二叉树中找到结点P的后继结点
void Inorder(ThreadTree);                     // 对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
ThreadNode *Lastnode(ThreadNode *);           // 找到以P为根的子树中最后一个被中序遍历的结点
ThreadNode *Prenode(ThreadNode *);            // 在中序线索二叉树中找到结点P的前驱结点
void RevInorder(ThreadTree);                  // 对中序线索二叉树进行逆向中序遍历(利用线索实现的非递归算法)
ThreadNode *Nextnode_PreBiTree(ThreadNode *); // 在先序线索二叉树中找到结点P的后继结点
void Preorder_PreBiTree(ThreadTree);          // 对先序线索二叉树进行先序遍历(利用线索实现的非递归算法)
ThreadNode *Prenode_PostBiTree(ThreadNode *); // 在后序线索二叉树中找到结点P的前驱结点
void RevPostorder_PostBiTree(ThreadTree);     // 对后序线索二叉树进行逆向后序遍历(利用线索实现的非递归算法)

ThreadNode *pre = NULL;

int main()
{
    ThreadTree root;
    PreCreateThreadTree(&root);
    Inorder(root);
    printf("\n");
    RevInorder(root);
    printf("\n");

    return 0;
}
void PreCreateThreadTree(ThreadTree *T) // 先序遍历创建二叉链表树
{
    ElemType ch;
    ch = getchar();
    getchar();
    if (ch == '.')
        *T = NULL;
    else
    {
        *T = (ThreadNode *)malloc(sizeof(ThreadNode));
        (*T)->data = ch;
        (*T)->ltag = 0;
        (*T)->rtag = 0;
        PreCreateThreadTree(&(*T)->lchild);
        PreCreateThreadTree(&(*T)->rchild);
    }
}
void visitAndBuildThread(ThreadNode *q) // 访问建立线索
{
    if (q->lchild == NULL)
    {
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}
void InThread(ThreadTree T) // 中序线索化
{
    if (T != NULL)
    {
        InThread(T->lchild);
        visitAndBuildThread(T);
        InThread(T->rchild);
    }
}
void PreThread(ThreadTree T) // 先序线索化
{
    if (T != NULL)
    {
        visitAndBuildThread(T);
        if (T->ltag == 0)
            PreThread(T->lchild);
        PreThread(T->rchild);
    }
}
void PostThread(ThreadTree T) // 后序线索化
{
    if (T != NULL)
    {
        PostThread(T->lchild);
        PostThread(T->rchild);
        visitAndBuildThread(T);
    }
}
void CreateInThread(ThreadTree T) // 中序线索化
{
    pre = NULL;
    if (T != NULL)
    {
        InThread(T);
        if (pre->rchild == NULL)
        {
            pre->rtag = 1;
        }
    }
}
void CreatePreThread(ThreadTree T) // 先序线索化
{
    pre = NULL;
    if (T != NULL)
    {
        PreThread(T);
        if (pre->rchild == NULL)
        {
            pre->rtag = 1;
        }
    }
}
void CreatePostThread(ThreadTree T) // 后序线索化
{
    pre = NULL;
    if (T != NULL)
    {
        PostThread(T);
        if (pre->rchild == NULL)
        {
            pre->rtag = 1;
        }
    }
}
void visit(ThreadTree T) // 访问输出结点
{
    printf("%c ", T->data);
    return;
}
ThreadNode *Firstnode(ThreadNode *p) // 找到以P为根的子树中第一个被中序遍历的结点
{
    while (p->lchild == 0)
        p = p->lchild;
    return p;
}
ThreadNode *Nextnode(ThreadNode *p) // 在中序线索二叉树中找到结点P的后继结点
{
    if (p->rtag == 0)
        return Firstnode(p->rchild);
    else
        return p->rchild;
}
void Inorder(ThreadTree T) // 对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)
{
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
    {
        visit(p);
    }
}
ThreadNode *Lastnode(ThreadNode *p) // 找到以P为根的子树中最后一个被中序遍历的结点
{
    while (p->rtag == 0)
        p = p->rchild;
    return p;
}
ThreadNode *Prenode(ThreadNode *p) // 在中序线索二叉树中找到结点P的前驱结点
{
    if (p->ltag == 1)
        return p->lchild;
    else
        return Lastnode(p->lchild);
}
void RevInorder(ThreadTree T) // 对中序线索二叉树进行逆向中序遍历(利用线索实现的非递归算法)
{
    for (ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p))
    {
        visit(p);
    }
}
ThreadNode *Nextnode_PreBiTree(ThreadNode *p) // 在先序线索二叉树中找到结点P的后继结点
{
    if (p->rtag == 1)
        return p->rchild;
    if (p->ltag == 0)
        return p->lchild;
    return p->rchild;
}
void Preorder_PreBiTree(ThreadTree T) // 对先序线索二叉树进行先序遍历(利用线索实现的非递归算法)
{
    for (T; T != NULL; T = Nextnode_PreBiTree(T))
    {
        visit(T);
    }
}
ThreadNode *Prenode_PostBiTree(ThreadNode *p) // 在后序线索二叉树中找到结点P的前驱结点
{
    if (p->ltag == 1)
        return p->lchild;
    if (p->rtag == 0)
        return p->rchild;
    return p->lchild;
}
void RevPostorder_PostBiTree(ThreadTree T) // 对后序线索二叉树进行逆向后序遍历(利用线索实现的非递归算法)
{
    for (T; T != NULL; T = Prenode_PostBiTree(T))
    {
        visit(T);
    }
}